import java.util.Arrays;

public class day230312 {
    //321. 拼接最大数
    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int[] maxArray = new int[k];

        // 第一个子序列 的元素个数区间
        int start = Math.max(0, k - n);
        int end = Math.min(k, m);

        // 遍历 这个区间的所有可能
        for (int i = start; i <= end; i++) {
            int[] maxArray1 = maxArray(nums1, i);
            int[] maxArray2 = maxArray(nums2, k - i);
            // 得到两个子序列拼接结果
            int[] curArray = merge(maxArray1, maxArray2);
            if (compare(curArray, 0, maxArray, 0) > 0) {
                maxArray = Arrays.copyOf(curArray, k);
            }
        }
        return maxArray;
    }

    // 单调栈的思想
    public static int[] maxArray(int[] nums, int k) {
        int[] stack = new int[k];
        // 栈顶下标
        int top = -1;
        // 记录可以删除的元素个数
        // 如果这个子序列有x个数
        // 我们只需要k个数
        // 那么可以省去的个数为 x - k
        // 保证不会删掉过多的元素, 最终能得到k个数
        int remain = nums.length - k;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            // 栈不为空, 栈顶元素小于 待入栈元素, 且可删除个数大于0
            while (top >= 0 && stack[top] < num && remain > 0) {
                // 删除栈顶元素
                // 可删除个数减1
                top--;
                remain--;
            }

            // 这里栈顶元素 是大于待入栈元素的
            // 或者栈为空
            if (top < k-1) {
                // 栈不满, 入栈
                stack[++top] = num;
            } else {
                // 栈满了, 这个元素就不要了, 可删除个数减1
                remain--;
            }
        }
        return stack;
    }

    // 拼接两个子序列
    public static int[] merge(int[] array1, int[] array2) {
        int x = array1.length;
        int y = array2.length;
        if (x == 0) {
            return array2;
        }
        if (y == 0) {
            return array1;
        }
        int mergeLength = x + y;
        int[] merged = new int[mergeLength];
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < mergeLength; i++) {
            if (compare(array1, index1, array2, index2) > 0) {
                merged[i] = array1[index1++];
            } else {
                merged[i] = array2[index2++];
            }
        }
        return merged;
    }

    // 比较两个子序列
    public static int compare(int[] array1, int index1, int[] array2, int index2) {
        int x = array1.length;
        int y = array2.length;

        while (index1 < x && index2 < y) {
            int different = array1[index1] - array2[index2];
            if (different != 0) {
                // 不相等
                return different;
            }
            index1++;
            index2++;
        }
        // 前面都相等
        // 比较剩余元素个数
        return (x - index1) - (y - index2);
    }

    public static void main(String[] args) {
        int[] nums1 = {7,6,1,9,3,2,3,1,1};
        int[] nums2 = {4,0,9,9,0,5,5,4,7};
        int[] ret = maxNumber(nums1, nums2, 9);
    }
}
